package com.backpack;

/**
 * 买卖股票的最佳时机含手续费
 * 输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
 * 输出：8
 * 解释：能够达到的最大利润:
 * 在此处买入 prices[0] = 1
 * 在此处卖出 prices[3] = 8
 * 在此处买入 prices[4] = 4
 * 在此处卖出 prices[5] = 9
 * 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
 */

/**
 * 思路同买卖股票二，无限多次交易，获取最大值，其中交易加上手续费
 */
public class BestTimetoBuyandSellStockwithTransactionFee0116_714 {
    public int maxProfit(int[] prices, int fee) {
        //动态规划思路
        // 买入时，出手续费
        //dp[i][0] 表示下标 i 天不持有该股票（售出） 手上的最大现金值为dp[i][0]
        //dp[i][1] 表示下标 i 天持有该股票（买入） 手上的最大现金值为dp[i][1]
        //返回值求： Math.max(dp[prices.length-1][0],dp[prices.length -1][1])
        int[][] dp = new int[prices.length][2];

        //初始化
        dp[0][0] = 0;
        dp[0][1] = -prices[0] - fee;

        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1] = Math.max(dp[i-1][0]-prices[i]-fee,dp[i-1][1]);
        }
        return Math.max(dp[prices.length-1][0],dp[prices.length -1][1]);
    }

}
